//https://leetcode.cn/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/submissions/589199383/
class Solution {
public:

    vector<int> ans;
    string las;
    vector<vector<int>> g;

    void dfs(int a, vector<int>& rec, int f) {
        // cout << a << endl;
        vector<int> rt(26, 0);
        for (auto x : g[a]) {
            if (x == f) continue;
            dfs(x, rt, a);
        }
        rt[las[a] - 'a']++;
        ans[a] = rt[las[a] - 'a'];
        for (int i = 0; i < 26; i++) rec[i] += rt[i];
    }


    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        ans = vector<int>(n);
        las = labels;
        vector<int> rts(26, 0);
        g = vector<vector<int>>(n);
        for (auto x : edges) {
            g[x[0]].push_back(x[1]);
            g[x[1]].push_back(x[0]);
        }
        dfs(0, rts, -1);
        return ans;
    }
};